package com.huangyi;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 最长递增子序列
    static class Solution {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            int[] dp = new int[n];
            Arrays.fill(dp, 1);  // 初始化：每个元素单独都是长度1

            // 从第二个元素开始遍历
            for (int i = 1; i < n; i++) {
                // 回头看所有前面的位置
                for (int j = 0; j < i; j++) {
                    // 如果能接在j后面，更新最大长度
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }

            // 找出所有位置中的最大值
            int ret = 0;
            for (int x : dp) {
                ret = Math.max(ret, x);
            }
            return ret;
        }
    }
}